#include <iostream>

using namespace std;

/*
连续的数据结构：vector<T>
  问题：在中间插入内容的时候，效率不好

不连续的数据结构
*/

// 先有一个自定义类型，表示节点
class Node {
public:
  // 节点里保存的值是什么？
  int value;

  // 节点的下一个节点在哪里？
  Node *next;

  // 定义构造函数
  Node(int v, Node *pn): value(v), next(pn) {
    cout << "A node with value " << v << "was created." << endl;
  }
};

class LinkedList {
public:
  // 头是什么？
  Node *head;

  // 创建一个以 h 作为头部的链表
  // 构造函数
  LinkedList() : head(nullptr) {}
  // 析构函数 - 在对象被销毁的时候自动调用
  ~LinkedList() {
    // 逐一归还我们申请过的节点
    // 我们应该按照什么顺序来归还？
    // delete 要删除的内容的位置;
    // 保存 head->next
    // delete head
    // 更新 head 指向下一个位置
    // 什么情况下，链表算是删干净了？ <-> head == nullptr
    Node *curr = head; // curr - 当前要删除的节点

    while (curr != nullptr) {
      cout << "节点值为: " << curr->value << "的 Node 被回收了." << endl;

      Node *next = curr->next;
      delete curr;

      head = next;
      curr = next;
    }

    cout << "LinkedList is deallocated." << endl;
  }


  // 如何能在链表的末尾添加 element？
  void push_back(int v) {
    // 1. 用 n 作为 value 创建一个 Node
    Node *pn = new Node {v, nullptr};

    // 2. 把这个创建出来的 Node 挂到链表上
    push_back(pn);
  }

  void push_back(Node *element) {
    // 从 head 开始向后遍历，直到链表的最后一个元素
    // 让它的 next 指向 element。
    if (head == nullptr) {
      head = element;
      return;
    }

    Node *pos = head;

    // 对于空链表来说 pos 也是 nullptr
    while (pos->next != nullptr) {
      pos = pos->next;
    }

    pos->next = element;
  }

  void print_list() {
    if (head == nullptr) {
      cout << "An empty list." << endl;
      return;
    }

    Node *pos = head;

    while (pos != nullptr) {
      cout << pos->value << " ";
      pos = pos->next;
    }
    cout << endl;
  }

  // bool find(int v) {
    
  // }

  // insert 在指定的节点后面添加一个新的节点
};

int main(int argc, char const *argv[])
{
  LinkedList l1; // 空链表 l1.head -> nullptr

  l1.push_back(1); // head -> 自动变量 n1 的地址
  
  l1.push_back(2); // head -> 自动变量 n1 -> 自动变量 n2

  // head
  // v
  // n1 -> n2 -> n3
  l1.push_back(3); 
  l1.print_list();

  return 0;
}
